This randomized clinical trial utilized established techniques to improve new learning and memory performance in multiple sclerosis (MS) participants with learning impairment. Participants were 29 individuals with clinically definite MS with documented learning deficits, randomly assigned to the experimental or control group. The experimental group underwent eight sessions of the Story Memory Technique (SMT), while the control group participated in eight sessions of memory exercises. Neuropsychological assessment was conducted at baseline, immediately following treatment and 5 weeks later to assess outcome. When stratifying participants by degree of learning deficits, a significant treatment effect was noted. MS participants with moderate-severe impairment in learning showed a significant improvement in learning abilities when compared to controls, (t(19) =3.32, P<0.01) evident in 88% of participants in the experimental group. Little improvement was noted in MS participants with mild learning impairments. Significant self-reported improvements in memory were noted in MS participants that underwent treatment, but not those that did not undergo treatment (t(26) =2.55, P<0.01). Results indicate that learning and memory deficits in MS can be effectively treated through a memory rehabilitation program utilizing context and imagery to improve new learning. Appropriate patient selection is important, with moderately-severely impaired individuals showing significantly greater benefit from treatment.